import java.util.Random;

public class Merge {
    public static void sort(Comparable[] a){
        Comparable[] aux = new Comparable[a.length];

//        原始的归并排序（自顶向下）
        sort(aux, a, 0, a.length -1);
//        第一种优化：
//        sort_update_1(aux, a, 0, a.length-1);
//        第二种优化：
//        sort_update_2(aux, a, 0, a.length-1);
    }

    private static void sort(Comparable[] aux, Comparable[] a, int lo, int hi){
        // 原始的归并排序
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(aux, a, lo, mid);
        sort(aux, a, mid+1, hi);
        merge(aux, a, lo, mid, hi);
    }

    private static void sort_update_1(Comparable[] aux, Comparable[] a, int lo, int hi){
        //第一种优化：对小规模数组使用插入排序
        if ((hi -lo) <= 10){
            // 当数组元素少于10时，使用插入排序
            insert_sort(a, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort_update_1(aux, a, lo, mid);
        sort_update_1(aux, a, mid+1, hi);
        merge(aux, a, lo, mid, hi);
    }

    private static void sort_update_2(Comparable[] aux, Comparable[] a, int lo, int hi){
        // 第二种优化：测试数组是否已经有序，如果a[mid] 小于等于a[mid+1], 我们认为数组已经有序，跳过merge()方法
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort_update_2(aux, a, lo, mid);
        sort_update_2(aux, a, mid+1, hi);
        if(less_or_equal(a[mid], a[mid+1])) return;
        merge(aux, a, lo, mid, hi);
    }

    private static void merge(Comparable[] aux, Comparable[] a, int lo, int mid, int hi){
        // 归并
        int i = lo;
        int j = mid + 1;
        System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        for (int k = lo; k <= hi; k++){
            if (i > mid) {
                a[k] = aux[j++];
            }else if (j > hi) {
                a[k] = aux[i++];
            }else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

    private static void insert_sort(Comparable[] a, int lo, int hi){
        // 插入排序
        for (int i = lo; i < hi; i++){
            Comparable temp = a[i];
            int j = i;
            while(j >= 1 && less(temp, a[j-1])){
                a[j] = a[j-1];
                j--;
            }
            a[j] = temp;
        }
    }

    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }

    private static boolean less_or_equal(Comparable v, Comparable w){
        return v.compareTo(w) <= 0;
    }
}
